1. Field of the Invention
The present invention relates to mutual exclusion in a computer system. More specifically, the present invention relates to a process for mutual exclusion for interrupt handling which is adaptive and reconfigurable in a computer system to an application program's requirements. 2. Backaround of Related Information
Computer systems require a means for servicing input/output devices such as keyboards, displays, sensors, and other components in order to allow the input/output device to communicate with the processor. One method of a processor communicating with input/output devices is shown in FIG. 1a. This is known as the "polled" method. A central processing unit 101 is coupled to a CPU-driven multiplexer 104 wherein each input/output device is selected and queried to determine if the device needs servicing. For instance, device 104, under control of CPU 101. will select over lines 105a, 106a, and 107a each of the input/output devices 105 through 107 and query those devices to determine whether each device needs servicing. This approach suffers from the disadvantage that a continuously executing process (multiplexer 104) is required by CPU 101, in order to ensure that each of the input/output devices is serviced regularly. This has a detrimental affect on system throughput because a large percentage of the processor overhead is consumed by such polling.
A more common and desirable method of computer system architecture used in most modem systems is the use of an interrupt. A block diagram of an interrupt-based system is shown as system 150 in FIG. 1b. Execution of instructions by a CPU such as 151 is continuous, and is only interrupted by a programmable interrupt controller (PIC) 154 when the controller determines that an input/output device needs servicing. PIC 154 is an overall manager which accepts requests from the I/O peripheral equipment, and determines which of the incoming requests has the highest importance (priority). PIC 154 ascertains whether the incoming request has a higher priority value than a current interrupt level, and may issue an interrupt to CPU 151 based upon this determination. For example, if an interrupt was being serviced for an input/output device 155, and an interrupt was issued by higher priority input/output device 156 over line 156a, then PIC 154 will issue an interrupt to CPU 151 over line 154a for servicing of input/output device 156. Then, communication with CPU 151 over bus 160 by input/output device 156 may be performed. Once an interrupt is detected by the CPU 151 over line 154a, an interrupt servicing routine sometimes known as an "interrupt handler" is called to service the device. In some prior art systems, each individual input/output device has its own interrupt handler which forms part of its device driver.
Various input/output devices have different priorities in interrupt-driven systems such as 150 shown in FIG. 1b. For example, in the original version of the UNIX.RTM. brand. operating system (UNIX.RTM. is a registered trademark of UNIX System Laboratories, Inc.), seven interrupts were provided in the system which were numbered 1 through 7. In the prior art UNIX.RTM. brand operating system, the higher the priority number, the higher the priority of the interrupt. A level 6 interrupt will therefore preempt a level 5 interrupt. For example, in the prior art UNIX.RTM. brand operating system, fixed input/output devices such as hard disk drives are assigned an interrupt level 5 and serial ternfinal lines are assigned an interrupt level 6 (note that these numbers vary for various versions of the UNIX.RTM. brand operating system).
Modem personal computers, such as those using the AT-type architecture, are designed. as single-user, single-tasking systems which are, in general, not interrupt-driven systems. Therefore, when porting the multi user. multitasking, interrupt-driven UNIX.RTM. brand operating system to a computer architecture system such as the AT platform, some architectural mismatches occur. For example, the UNIX.RTM. brand operating system uses seven prioritized interrupt levels, however, the AT-type architecture has a master and one or more slaved 8259A-type programmable interrupt controllers (PIC's) that, although also prioritized, do not correspond with those used in UNIX.RTM. (the 8259A PIC is available from Intel Corporation of Santa Clara, Calif.). In FIG. 1b, the 8259A PIC's are shown as 154. In the prior art UNIX.RTM. brand operating system which is desired to be ported to an AT-type system, serial devices utilize interrupts 2 and 5, which correspond to the UNIX.RTM. brand operating system's level 6. A hard disk or other fixed media disk drive has an interrupt 14 on the AT system which corresponds to the UNIX.RTM. level 5. One 8259A brand PIC can mask each of its interrupt lines in order to simulate a UNIX.RTM. interrupt priority level by preventing the acknowledgement of interrupts from lower priority devices. A detailed description of the programming of the 8259A PIC may be found in the publication Intel Peripheral Components (1991), available from Intel Corporation Literature Sales, P.O. Box 7641, Mount Prospect, Ill. 60056-7641 (hereinafter "Peripheral Components"). In order to port an operating system such as UNIX.RTM. to an AT-type architecture, during run-time, interrupts for certain devices having a lower priority in UNIX.RTM. may be prevented from being acknowledged by reprogramming PIC's 154 when servicing higher level devices. This reprogramming suffers from some drawbacks, however.
Prior art interrupt controllers employing these techniques, such as the 8259A PIC, suffer from performance problems due to the latency involved in programming the controller. In addition, in order to ensure that the PIC works properly, a reprogramming operation must also wait a period of time for circuitry within the controller to settle in order to process interrupts reliably. In certain PIC's such as the 8259A, after programn-fing is complete, approximately one microsecond must transpire prior to executing any additional code. Interrupt handling will therefore take approximately one microsecond longer. Note that in a system containing multiple PIC's (the original AT-type platform contains two) the reprogramming operation will have to wait one microsecond after the last PIC is programmed. to allow all the PIC's to settle. In modern systems with processors operating at faster speeds, this poses a serious processing bottleneck.
UNIX.RTM. brand operating system device drivers operate as a collection of cooperating "threads." Most of these correspond to the notion of "processes" as generally used in discussions of this operating system. These processes operate at the lowest priority, priority zero. A device driver in this system has a higher priority thread for each hardware interrupt used by the device(s) being controlled. In general, this interrupt thread has the responsibility for manipulating the device (since it is synchronized with the device by the interrupt itself). The main task of the process threads is to communicate with the interrupt thread. Such communication is accomplished by means of shared data structures in the computer system memory. When multiple threads desire to modify shared data structures, a mutual exclusion problem is raised. This problem is solved in the device driver case by the use of functions entitled splN() and splx() in the UNIX.RTM. brand operating system. Spl() functions or "system priority level" functions are used for setting or resetting interrupt priority levels in the UNIX.RTM. brand operating system which will be recognized. A detailed discussion of the spl() functions are found in the publication entitled "UNIX.RTM. System V, Release 4: Device Driver Interface/Driver-Kemel Interface Reference Manual for Intel Processors" available from UNIX System Laboratories, Inc. Corporate Sales of Engwood CliffS, N.J. (hereinaftcr "Driver-Kernel Manual"). Essentially, splN() acquires a read/write lock on all data structures of priority N or lower. The splint() function restores the data structure to the previous exclusion level. The PIC and similar external hardware in the system is used to prevent devices from causing interrupts which should not be taken because their interruler routines would deadlock on this read/write lock.
While the description which follows relates the discussion of the interrupt subsystem, it is clear that the techniques described here have equal applicability to some instances of the larger problem of mutual exclusion where it is difficult or expensive to inform some processes or devices that a lock is present.
One prior art method of blocking interrupts for AT-type systems running the UNIX.RTM. brand operating system is shown and discussed with reference to FIG. 2. This prior art method of interrupt processing is performed by reprogramming the PIC in the system every time code is executed in order to mask or prevent lower priority interrupts from occurring. This prior art process shown in FIG. 2 suffers from the disadvantage that it unnecessarily programs the PIC even when no lower priority interrupt later occurs. Therefore, processing bandwidth is consumed by programming the PIC when it is sometimes not necessary. For example, process 200 starts at step 201 and sets the desired interrupt priority level at step 202. First, the operating system calls an appropriate "spl()" (such as splN()) function in the UNIX.RTM. brand operating system in order to block or allow servicing of interrupts by the operating system. The spl() function will reprogram the PIC to mask all interrupts having a priority level less than the priority level set at step 202. This is accomplished in some prior art personal computers and workstations using the UNIX.RTM. brand operating system by programming PIC's such as 154 shown in FIG. 1b, by calling an outb() function which writes a byte to an 8-bit input/output port on the processor to the PIC. This function is discussed in Driver-Kernel Manual. Note that the reprogramming process discussed with reference to steps 203,207,209, and 211 in FIG. 2, all include an outb() function call tollowed by an inb() function which attempts to gad from the I/O port on the processor that the PIC is coupled to. This allows the PIC to settle prior to executing any additional code. The inb() instruction will not be able to read from the I/O port until the circuitry has settled, which in the prior art, typically takes an additional microsecond. Each reprogramming operation will therefore consume at least one additional microsecond in addition to the time it takes to program the PIC.
After reprogramming the PIC Lit step 203, the protected code is then executed at step 204. After the start of code execution. an interrupt may be asserted by a lower priority device at step 205 but, because the PIC has been reprogrammed to ignore these interrupts, they are not recognized, and therefore, not serviced. The CPU in the system never receives the interrupt. Then, at step 206, the splx() function is called in order to reset the priority level of the interrupts in the operating system kernel to the state it was in prior to step 202. Then, the PIC is reprogrammed again at step 207 to allow the interrupts previously masked out to be recognized. Again, as discussed with reference to step 203 above, this process is performed using the outb() instruction to write to the 8-bit I/O port, and is followed by an inb() instruction to allow the PIC to settle. Then, at step 208, the interrupt previously masked is recognized by the PIC, and, at step 209, the PIC is again reprogrammed for a new interrupt priority level as in step 202 above. This is to prevent any other lower priority interrupts from occurring. At step 210, the interrupt handler for any pending interrupts which were masked by the PIC at step 203 is called to service the interrupting device. At step 211, the PIC is then again reprogrammed to tile state it was in prior to step 202. Then, at step 212, process 200 returns from the interrupt, and process 200 ends at step 213. As shown in process 200, the PIC has been reprogrammed a total of four times in this prior art method, thus incurring substantial latency due to the time required for reprogramming the PIC, and the time required for waiting for tile PIC circuitry to settle. In addition, if no interrupt occurs (such as occurred at step 208), the PIC has been unnecessarily programmed two times at steps 203 and 207. In othcr words, because no interrupt at all occurred, the PIC needn't have been reprogrammed. These reprogramming and waiting operations consume substantial processor overhead and reduce overall performance of the system unnecessarily.
Thus, substantial performance penalties are incurred in prior art interrupt handling techniques especially while attempting to map interrupt priorities for one operating system designed for one computer architecture to another.